\|\\M0basl30;\M2germ35;\M9fix20;\←=90;\ε\`'10004;\F0\;

2.	Conventional Cryptography and IFF

\J	Figure  1  illustrates  the  flow  of  information  in  a   conventional
cryptographic system.    As shown there, the system consists of three parties: a
transmitter, a legitimate receiver, and a  cryptanalyst.        The  transmitter
generates  a plaintext or unenciphered message P which must be communicated over
an insecure channel to the legitimate receiver.      In  order  to  prevent  the
cryptanalyst  from  learning  P the transmitter operates on P with an invertible
transformation T\∪K\⊗, dependent on a  key  K,  to  produce  the  ciphertext  or
cryptogram  C  =  T\∪K\⊗(P).   The transformation T\∪K\⊗ is chosen from a set of
invertible transformations {T\∪k}\∪k=1\∩M\⊗, where M is the number of keys.   It
is  assumed  that  the cryptanalyst knows the general system in use, that is the
set {T\∪k\⊗}.  He does not, however, know which of the M  specific  keys  is  in
use.    Rather,  on  the  basis of C and certain side information he attempts to
solve for P and/or K. As an example, the side information is often a knowlege of
the language in use.  Other forms of side information will be discussed shortly.
The key K is transmitted only to the legitimate receiver via a  secure  channel,
indicated  by  shielded cable in figure 1.  The secure channel cannot be used to
transmit P itself for reasons of capacity or delay.   For  example,  the  secure
channel  may  be  a weekly courier while the insecure channel may be a telephone
line. Since the legitimate receiver knows the  key  K,  he  can  decipher  C  by
operating  with T\∪K\⊗\∩-1\⊗ to obtain T\∪K\⊗\∩-1\⊗(C) = T\∪K\∩-1\⊗(T\∪K\⊗(P)) =
P, the original plaintext message.
	Our  goal  in  designing the cryptosystem {T\∪k\⊗} is to ensure that the
enciphering and deciphering  operations  are  not  too  complex,  but  that  any
successful  cryptanalytic operation is so complex that it cannot be economically
implemented.    For  example  if  successful  cryptanalysis  required  10\∩100\⊗
arithmetic  operations  we would rest assured of our system's security. A system
which is secure due to the computational cost of cryptanalysis, but which  would
succumb  to  an  attack  with  unlimited  computation is called _computationally
secure_. This is opposed to an _unconditionally secure_ system which can  resist
all   cryptanalytic   attacks,  no  matter  how  much  computation  is  allowed.
Unconditionally secure systems are discussed in [,], and belong to that  portion
of  information  theory,  often  called  Shannon theory, which is concerned with
optimal  performance  obtainable  with  unlimited  computation.    Unconditional
security  results  when  there  are  a large number of meaningful solutions to a
cryptogram (eg. the simple substitution cryptogram  XM  resulting  from  English
text, can represent the plaintext message NO, HI, OW, etc.).
	Perhaps the only unconditionally secure system in use is  the  one  time
pad,  in which a binary representation of the plaintext is exclusive-or'd with a
randomly chosen binary key of the same length. While such a system  is  provably
secure,  the  large  amount  of  key  required  makes  it  impractical  for most
applications.  This  paper  is  concerned  solely  with  computationally  secure
systems  since  they are more generally applicable.  Thus when we talk about the
need to develop provably secure cryptosystems we exclude those, such as the  one
time  pad,  which  are  unwieldly to use in most applications. Rather we have in
mind a system using less than 1000 bits of key, and which could  be  implemented
on  one or several special purpose chips (or which would take only a few hundred
lines of code and reasonable compute time in a software implementation).

	It is difficult to assess the computational security of a system under a
\{statistical  attack\}=2;=2; in which the cryptanalyst only knows the structure
of the language in which the plaintext was written, and uses its  redundancy  to
find  a  unique  meaningful solution.    For example, a statistical attack on an
English language simple substitution cipher makes use of the frequent occurrence
of E, T, etc. and the infrequent occurrence of Z, Q, etc.

	When dealing with computational security we will consider instead either
a \{known plaintext attack\}=2;=2; or a \{chosen plaintext attack\}=2;=2;.  In a
known plaintext attack, the analyst has a number of P-C pairs, all in  the  same
key.    His  task is to determine the key so that he can easily decipher all new
cryptograms  written  in  that  key.    This  is  equivalent   to   the   system
identification  problem of deducing the parameters of a system, in this case the
key, from input-output pairs.   Since it is more formidable than  a  statistical
attack,  using  it  as  our  threat  model is desirable since it produces a more
conservative estimate of the system's strength. And, as we shall see,  it  often
allows a more precise, mathematical statement of the cryptanalytic problem.
	The chosen plaintext attack is  derived  from  use  of  cryptography  in
aircraft  IFF  (identification  -  friend  - or - foe) systems.  Being even more
formidable  than  the  known  plaintext  attack,  it  produces  an   even   more
conservative  estimate  of  the  cryptosystem's strength. In such an attack, the
cryptanalyst is given cryptograms resulting from plaintext messages of  his  own
choosing.    Again,  his  task  is  to determine the key.  This is also a system
identification problem, except now an active role is taken by  the  cryptanalyst
in   choosing   the   system   inputs.      He   can   generate  as  many  known
plaintext-cryptogram pairs as he desires, and if there is a "natural  coordinate
system"  for  the {T\∪k\⊗}, he can use the basis vectors to easily determine the
key.  For example if P and C are both binary n-vectors and {T\∪k\⊗} is  the  set
of  all invertible, binary, nXn matrices then by enciphering the n unit vectors,
(1,0,...,0) through (0,...,0,1), the cryptanalyst obtains the n columns  of  the
matrix T\∪K\⊗ and therefore the key being used.
	Known,  or  partially  known,  plaintext  attacks  frequently  occur  in
practice,  and  any cryptosystem which cannot resist them is truly insecure.  In
diplomatic correspondence, for example, a proposal is often sent  in  enciphered
form  and  later  presented  time  to one's opponents in plain language. Obvious
commercial analogs, such  as  press  releases  and  product  announcements,  are
examples  of the previously mentioned problem that old plaintext messages may be
delcassified.
	Chosen  plaintext  attacks,  on the other hand, rarely occur in practice
and are used primarily as a conservative test of system strength.
	At   this   point  we  turn  to  a  brief  review  of  conventional  IFF
(identification - friend - or - foe) systems. Early versions  of  these  systems
were first used during the Second World War to distinguish automatically between
friendly and enemy aircraft.  In order to be recognized  by  a  friendly  radar,
each  aircraft  carried  a  transponder  designed to listen specifically for the
radar's signal and respond by transmitting a special codeword or signal, telling
the radar of its friendliness.

	The weaknesses of this system are easily seen.   Enemy intelligence need
only listen to one such exchange in order to learn the airplane's codeword,  and
gain  the  ability to send an imposter.  As one defense against this threat, the
codeword used by The aircraft can be changed  frequently  according  to  complex
prearranged schedules, a tedious burden to an already busy pilot.
	A cryptographic approach greatly  simplifies  matters.     The  airplane
carries  only  one  "codeword",  which  is in reality a cryptographic key. It is
never transmitted as a response and never changed during flight.   In  order  to
determine  the  identity  of  an  aircraft  the radar must, as before send out a
challenge to the aircraft.   Now, however, the challenge is not a constant  "Who
are  you?"  but  is  a  time  dependant  random  bit  pattern which changes from
challenge to challenge. The aircraft enciphers the challenge and sends it  back.
In  order  to  judge  whether  it was correctly enciphered, thereby indicating a
friendly plane, the radar deciphers  the  response  and  compares  it  with  the
original  challenge.    If it agrees the airplane was friendly, otherwise it was
hostile.    If  each  plane  is  provided  with  a  different  key,  then  exact
identification is possible.


	Use of this type of challenge and response authentication, can present a
far  more  severe  challenge  to a cryptosystem than does normal communications.
While the aircraft is within range, enemy radar can challenge  it  as  often  as
desied  with  challenges  of  the  enemy's  choosing.   The cryptosystem must be
strong enough to protect the key even under such a severe test.
	The  development  of  the  chosen plaintext attack, which marked a major
advance in, certificaton via cryptanalysis, descends from the IFF problem. It is
possible  to limit such an attack on an IFF system by restricting the challenges
to be a function of the date and time.
	Cryptographic  systems  for computer networks can be modeled on military
systems, but require modifications because of their different environment.   The
most  prominent  difference  is  that  users of a commercial network continually
change their allegiances. While communicating with each other, users A and B may
regard  a third user C as a potential threat and wish to prevent him from either
impersonating one of them or eavesdropping.   Later, if A  communicates  with  C
they  may  regard B as a potential threat. There is a need for any pair of users
to be able to verify each other's identity and communicate  privately.   Use  of
converntional  cryptography  results in a horrendous key distribution problem in
even a moderate sized network.
	The  next  section introduces a number of new problems and techniques in
data security which may eliminate problems such as these.